A cache is a memory for temporary storage of data in a data processing apparatus. Commonly, a cache is a smaller, high-speed memory that stores copies of a subset of data from a backing storage device. The backing storage device is typically a larger, slower memory or data storage device. The data in the cache is used by a cache client, such as a central processing unit (CPU). Performance of the CPU is enhanced when often used data is available in the cache, thus avoiding latency associated with reading data from the backing storage device. Each entry in the cache includes the data itself together with a tag associated with the location of the original data in the backing storage device, a validity bit and, optionally, one or more status bits. The size of a cache is determined by the need to store the tags, validity and status bits in addition to the data itself.
For large caches, a large tag store is required. For example, for a large off-chip DRAM cache the tag storage requirements can often exceed what can practically be stored in on-chip SRAM. Storing the tags in DRAM itself, however, has a big latency penalty as both tags and data need to be read from the DRAM, and DRAM access is much slower than SRAM access.